import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        nodeE.right = nodeH;
        return nodeA;
    }

    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public List<TreeNode> preOrder1 (TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        list.add(root);
        list.addAll(preOrder1(root.left));
        list.addAll(preOrder1(root.right));
        return list;
    }


    public void inOrder (TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public List<TreeNode> inorderTraversal(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root);
        list.addAll(inorderTraversal(root.right));
        return list;
    }

    public void postOrder (TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public List<TreeNode> postorderTraversal(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root);
        return list;
    }

    public int size;
    public void getSize1 (TreeNode root) {
        if (root == null) return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }
    public int getSize2 (TreeNode root) {
        if (root == null) return 0;
        return getSize2(root.left) + getSize2(root.right) + 1;
    }
    public int leafSize;
    public void getLeafSize1 (TreeNode root) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }
    public int getLeafSize2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return  getLeafSize2(root.left) + getLeafSize2(root.right);
    }
    public int getKLevelSize (TreeNode root,int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelSize(root.left,k - 1) +
                getKLevelSize(root.right,k - 1);
    }
//    public int getHeight (TreeNode root) {
//        if (root == null) return 0;
//        int leftHigh = getHeight(root.left);
//        int rightHigh = getHeight(root.right);
//        return leftHigh > rightHigh ? leftHigh + 1 :
//                rightHigh + 1;
//    }
    public int getHeight (TreeNode root) {
        if (root == null) return 0;
        int leftHigh = getHeight(root.left);
        int rightHigh = getHeight(root.right);
        if (leftHigh >= 0 && rightHigh >= 0 && Math.abs(leftHigh - rightHigh) <= 1) {
            return Math.max(leftHigh,rightHigh) + 1;
        }else {
            return -1;
        }
    }
}
